/*
 * @lc app=leetcode.cn id=501 lang=cpp
 *
 * [501] 二叉搜索树中的众数
 *
 * https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/description/
 *
 * algorithms
 * Easy (52.98%)
 * Likes:    448
 * Dislikes: 0
 * Total Accepted:    95.4K
 * Total Submissions: 180K
 * Testcase Example:  '[1,null,2,2]'
 *
 * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
 * 
 * 如果树中有不止一个众数，可以按 任意顺序 返回。
 * 
 * 假定 BST 满足如下定义：
 * 
 * 
 * 结点左子树中所含节点的值 小于等于 当前节点的值
 * 结点右子树中所含节点的值 大于等于 当前节点的值
 * 左子树和右子树都是二叉搜索树
 * 
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root = [1,null,2,2]
 * 输出：[2]
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root = [0]
 * 输出：[0]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 树中节点的数目在范围 [1, 10^4] 内
 * -10^5 <= Node.val <= 10^5
 * 
 * 
 * 
 * 
 * 进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {

    //采用哈希表unordered_map的方式
// private:
//     void traversalBST(TreeNode* root, unordered_map<int, int>& map) {
//         if(root == NULL) return;

//         traversalBST(root->left, map);
//         auto iter = map.find(root->val);
//         map[root->val]++;
//         //以下这种方法效率太低了，不如上边这种方法
//         // if(iter != map.end()) iter->second++;
//         // else map.insert(pair<int, int>(root->val, 1));
//         traversalBST(root->right, map);
//         return;
//     }

//     bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {
//         return a.second > b.second;
//     }
// public:
//     vector<int> findMode(TreeNode* root) {
//         unordered_map<int, int> map;
//         vector<int> res;
//         traversalBST(root, map);

//         vector<pair<int, int>> vec(map.begin(), map.end());

//         sort(vec.begin(), vec.end(), cmp);

//         res.push_back(vec[0].first);

//         for(int i = 1; i < vec.size(); i++) {
//             if(vec[i].second < vec[0].second) break;
//             res.push_back(vec[i].first);
//         }

//         return res;
//     }


private:
    TreeNode* pre = NULL;
    int maxCount = 1;
    int valCount = 1;

    void traversal(TreeNode* cur, vector<int>& vec) {
        if(!cur) return;

        if (cur->left) traversal(cur->left, vec);

        // 以下我的操作,反复考虑的情况太多，太多的if
        // 是可行的
        // if(pre) {
        //     // 当pre存在的情况
        //     if(cur->val == pre->val) {
        //         //pre存在，而且，与上一个节点的值相同，
        //         valCount++;
        //         if(valCount == maxCount) {
        //             //r如果次数相等，吧当前节点的值，push_back进去
        //             vec.push_back(cur->val);
        //         } else if (valCount > maxCount) {
        //             //如果当前节点的次数大于最大次数，清空，并push_back进去
        //             maxCount = valCount;
        //             vec.clear();
        //             vec.push_back(cur->val);
        //         }
        //     } else {
        //         valCount = 1;
        //         if(maxCount == valCount) vec.push_back(cur->val);
        //     }
        // } else {
        //     //pre不存在的情况，第一个节点
        //     vec.push_back(cur->val);
        // }
        // pre = cur;

        // 代码随想录中答案
        if(pre == NULL) {
            //此时是第一个元素
            valCount = 1;
        } else if (cur->val == pre->val) {
            //此时不是第一个元素，而且，与前一个节点的数值相同
            valCount++;
        } else {
            //此时不是第一个元素，而且，与前一个节点的数值不同
            valCount = 1;
        }

        //处理完了节点，吧当前的节点变成之前的节点
        pre = cur;

        if(valCount == maxCount) {
            vec.push_back(cur->val);
        } else if (valCount > maxCount) {
            maxCount = valCount;
            vec.clear();
            vec.push_back(cur->val);
        }


        if (cur->right) traversal(cur->right, vec);
        
        return;

    }

public:
    vector<int> findMode(TreeNode* root) {
        if(root == NULL) return {};
        vector<int> res;
        traversal(root, res);
        return res;
    }


};
// @lc code=end

